import functools
class Solution(object):
    def minimumWhiteTiles(self, floor, numCarpets, carpetLen):
        @functools.cache
        def dfs(i, k):
            if i < 0:
                return 0
            else:
                if k == 0:
                    return dfs(i - 1, k) + (floor[i] == '1')
                else:
                    return min(dfs(i - carpetLen, k - 1), dfs(i - 1, k) + (floor[i] == '1'))
        return dfs(len(floor) - 1, numCarpets)


data = Solution()
floor = "10110101"
numCarpets = 2
carpetLen = 2
print(data.minimumWhiteTiles(floor, numCarpets, carpetLen))